package com.demo.java.OD251_300.OD273;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【统一限载货物数最小值】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146074245
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取货物数量
        int num_goods = sc.nextInt();
        int[] goods = new int[num_goods];
        int[] types = new int[num_goods];

        // 读取货物重量
        for (int i = 0; i < num_goods; i++) {
            goods[i] = sc.nextInt();
        }

        // 读取货物类型 (干货为0，湿货为1)
        for (int i = 0; i < num_goods; i++) {
            types[i] = sc.nextInt();
        }

        // 读取货车数量
        int num_vans = sc.nextInt();

        // 分别保存干货和湿货
        List<Integer> dry_goods = new ArrayList<>();
        List<Integer> wet_goods = new ArrayList<>();
        int total_dry_weight = 0;
        int total_wet_weight = 0;

        // 分类货物为干货和湿货
        for (int i = 0; i < num_goods; i++) {
            if (types[i] == 0) {
                dry_goods.add(goods[i]);
                total_dry_weight += goods[i];
            } else {
                wet_goods.add(goods[i]);
                total_wet_weight += goods[i];
            }
        }

        // 对干货和湿货分别排序
        Collections.sort(dry_goods);
        Collections.sort(wet_goods);

        // 分别计算干货和湿货的最小承载能力
        int min_dry_van_capacity = dry_goods.isEmpty() ? 0 : findMinVanCapacity(dry_goods, total_dry_weight, num_vans);
        int min_wet_van_capacity = wet_goods.isEmpty() ? 0 : findMinVanCapacity(wet_goods, total_wet_weight, num_vans);

        // 输出两者的最大值，作为最小承载能力
        System.out.println(Math.max(min_dry_van_capacity, min_wet_van_capacity));
    }

    // 计算最小的货车承载能力
    public static int findMinVanCapacity(List<Integer> goods, int total_count, int num_vans) {
        int max_good_weight = Collections.max(goods); // 获取最大单个货物重量
        int min_van_capacity = Math.max(max_good_weight, total_count / num_vans + (total_count % num_vans == 0 ? 0 : 1)); // 最小承载能力

        int max_van_capacity = total_count; // 最大承载能力

        // 使用二分查找来找到最小的承载能力
        while (min_van_capacity < max_van_capacity) {
            int mid = (min_van_capacity + max_van_capacity) / 2; // 中间值
            int[] vans = new int[num_vans]; // 初始化货车状态
            if (check(goods, 0, vans, mid)) { // 检查是否可以用当前承载能力装载货物
                max_van_capacity = mid; // 如果可以，缩小最大承载能力范围
            } else {
                min_van_capacity = mid + 1; // 否则，增大最小承载能力范围
            }
        }

        return min_van_capacity;
    }

    // 递归检查是否能在当前承载能力下分配货物
    public static boolean check(List<Integer> goods, int index, int[] vans, int weight) {
        if (index == goods.size()) { // 如果所有货物都已分配，返回true
            return true;
        }
        for (int i = 0; i < vans.length; i++) {
            if (i > 0 && vans[i] == vans[i - 1]) {
                continue; // 如果当前货车和前一个货车相同，跳过
            }
            if (vans[i] + goods.get(index) <= weight) { // 如果可以装载当前货物
                vans[i] += goods.get(index);
                if (check(goods, index + 1, vans, weight)) {
                    return true;
                }
                vans[i] -= goods.get(index); // 回溯
            }
        }
        return false; // 如果无法分配，返回false
    }
}